Problem statement: zenit12cki

Na stretnutí farmárov sa každoročne uskutočňuje súťaž o najťažšiu tekvicu. Každý prinesie svoj najúspešnejší kus, ktorý sa následne stretne na váhe s protivníkmi. Najťažšia tekvica znamená ohromnú prestíž a je snom každého pestovateľa. Tento rok sa prihlásil aj Lukáš s výsledkom svojej starostlivej práce. Po pokorení programátorského a tanečného sveta naďalej hľadá v živote nové výzvy.

Súťaž má trošku nelogickú organizáciu - takzvaného pavúka, ktorého poznáme napríklad z tenisových turnajov. Na začiatku sú súťažiaci rozdelení do dvojíc. V rámci súboja dvojice každý odváži svoju tekvicu. Ťažšia z tejto dvojice triumfálne postupuje do ďalšieho kola. V tomto kole je víťaz prvej dvojice konfrontovaný s víťazom druhej dvojice. Víťaz tohto zápolenia je konfrontovaný s víťazom druhej štvorice (to znamená tretej a štvrtej dvojice v počiatočnom rozdelení) a takto sa postupuje, až kým neostane len jedna tekvica. Samozrejme, pekne to vychádza vtedy a len vtedy, ak je počiatočný počet tekvíc mocnina dvojky.

Každý súboj dvojice tekvíc má nejakú športovú hodnotu. Táto hodnota je definovaná ako súčet hmotností vážených tekvíc. Hodnota turnaja je súčtom hodnôt všetkých súbojov dvojíc. Ako ukazujú aj naše príklady nižšie, hodnota turnaja môže byť rôzna pri rôznom počiatočnom rozostavení.

Lukáš sa ako šikovný hacker dostal do počítača organizátorov. Okrem iného tak získal možnosť upraviť štartovné pole. Lukášov primárny cieľ je vyhrať. Sekundárny cieľ je vyhrať čo najhodnotnejší turnaj.

Na prvom riadku vstupu je počet súťažiacich tekvíc N. Toto číslo je mocnina dvojky a platí 2 ≤ N ≤ 200,000. Na ďalších N riadkoch je zoznam súťažiacich: meno farmára a hmotnosť jeho tekvice. Meno farmára pozostáva z malých a veľkých znakov anglickej abecedy a jeho dĺžka je aspoň 1 a nepresahuje 20 znakov. Hmotnosť tekvice je prirodzené číslo, ktoré nepresahuje 1,000,000. Žiadne dve mená nebudú rovnaké. Žiadne dve hmotnosti nebudú rovnaké. Práve jedno meno bude Lukas.

V prípade, že Lukáš nemôže vyhrať turnaj pri žiadnom počiatočnom rozostavení, vypíšte NEDA SA. V opačnom prípade vypíšte na prvý riadok výstupu jedno číslo: najväčšiu možnú hodnotu turnaja pri rozostavení, ktoré je pre Lukáša víťazné. Na ďalších N/2 riadkoch vypíšte počiatočné rozostavenie turnaja, ktoré túto hodnotu dosahuje. Ak je možností viac, vypíšte ľubovoľnú z nich. Na poradí súťažiacich vo dvojici nezáleží. Pozor, možno nebude stačiť 32-bitová premenná! Riešenia v Pythone síce možno pobehajú, ale nebudú to mať jednoduché.

4
Mirko 50
Marosko 60
Lukas 80
MisoF 70

    
  

410
Lukas - Mirko
Marosko - MisoF

    
  

8
Zemco 60
Lukas 100
MisoF 35
Bob 90
Sysel 40
Jano 70
Anicka 80
Hermi 20

    
  

1025
Lukas - Zemco
Anicka - MisoF
Sysel - Bob
Hermi - Jano

    
  

2
Lukas 150
Petr 200

    
  

NEDA SA